package org.data.collection.tree.basic;

import cn.hutool.core.util.ObjectUtil;
import lombok.Data;
import lombok.ToString;
import org.data.collection.tree.basic.interfaces.Tree;
import org.data.collection.tree.enums.Traverse;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

import static cn.hutool.core.util.ObjectUtil.isNull;
import static org.data.collection.tree.enums.Traverse.ROOT_TRAVERSAL;

/**
 * 二叉树的抽象父类
 *
 * @author LiKun
 * @date 2021/11/22 19:33
 */
@ToString
public abstract class BinaryTree<K, V> implements Tree<K, V> {
    /**
     * 树-根节点
     */
    protected volatile Entry<K, V> root;

    /**
     * 数据节点个数
     */
    protected AtomicInteger size = new AtomicInteger();

    /**
     * 树-构造-比较器
     */
    protected volatile Comparator<? super K> comparator;

    @Override
    public int getSize() {
        return size.intValue();
    }

    @Override
    public K getRootKey() {
        return this.root.key;
    }

    @Override
    public V getRootValue() {
        return this.root.value;
    }

    /**
     * 根据 Key 获取 Entry 节点
     *
     * @param key Key值
     *
     * @return Entry节点
     */
    public abstract Entry<K, V> getEntry(K key);

    public List<Entry<K, V>> rootTraversal(K key) {
        List<Entry<K, V>> entries = Collections.emptyList();
        Entry<K, V> start = isNull(key) ? root : getEntry(key);

        if (ObjectUtil.isNotNull(start)) {
            entries = new ArrayList<>(size.intValue());
            entries.add(start);

            this.traverseTree(start, entries, ROOT_TRAVERSAL);
        }

        return entries;
    }

    /**
     * 比较 curKey 和 preKey 的顺序
     *
     * @param curKey 当前 Key 值
     * @param preKey 被比较的 Key 值
     *
     * @return 比较结果
     */
    protected int compare(K curKey, K preKey) {
        return ObjectUtil.isNotNull(comparator) ? comparator.compare(curKey, preKey)
                : ((Comparable<? super K>) curKey).compareTo(preKey);
    }

    /*------------------------------------------------private methods-------------------------------------------------*/

    /**
     * 根据遍历方式遍历以当前节点为根节点的树结构
     *
     * @param entry    当前节点
     * @param entries  存储数据的集合
     * @param traverse 遍历方式
     */
    private void traverseTree(Entry<K, V> entry, List<Entry<K, V>> entries, Traverse traverse) {
        Entry<K, V> childEntry = null;
        if (ROOT_TRAVERSAL.equals(traverse)) {
            if (ObjectUtil.isNull(childEntry = entry.leftTree)) {
                childEntry = entry.rightTree;
            }
            if (ObjectUtil.isNotNull(childEntry)) {
                entries.add(childEntry);
                this.traverseTree(childEntry, entries, traverse);
            }
        }
    }

    /*--------------------------------------------------Inner Class---------------------------------------------------*/

    @Data
    public static final class Entry<T, S> {
        /**
         * 节点 Key
         */
        protected T key;

        /**
         * 节点 Value
         */
        protected S value;

        /**
         * 节点左子树
         */
        protected Entry<T, S> leftTree;

        /**
         * 节点右子树
         */
        protected Entry<T, S> rightTree;

        public Entry(T key, S value) {
            this.key = key;
            this.value = value;
        }

        public Entry(T key, S value, Entry<T, S> leftTree) {
            this(key, value);
            this.leftTree = leftTree;
        }

        public Entry(T key, S value, Entry<T, S> leftTree, Entry<T, S> rightTree) {
            this(key, value);
            this.leftTree = leftTree;
            this.rightTree = rightTree;
        }
    }
}
